package com.zbxx.leetcode.tree;

import com.zbxx.leetcode.struct.TreeNode;


/**
 * 654 最大二叉树
 *
 * @author wanrj
 * @date 2023/6/5
 */
public class constructmaximumbinarytree {

    public TreeNode constructMaximumBinaryTree(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    public TreeNode build(int nums[], int start, int right) {
        if (start > right) {
            return null;
        }
        if (start == right) {
            return new TreeNode(nums[start]);
        }
        int max = find(nums, start, right);
        TreeNode node = new TreeNode(nums[max]);
        node.left = build(nums, start, max - 1);
        node.right = build(nums, max + 1, right);
        return node;
    }

    public int find(int nums[], int start, int right) {
        int max = start;
        for (int i = start + 1; i <= right; i++) {
            if (nums[i] > nums[max]) {
                max = i;
            }
        }
        return max;
    }


    public static void main(String[] args) {
        constructmaximumbinarytree c = new constructmaximumbinarytree();
        c.constructMaximumBinaryTree(new int[]{3, 2, 1, 6, 0, 5});
    }


}
